package leetcode_500;

public class TargetSum_494 {
	int res=0;
	/**
	 * describe:回溯法 暴力解 AC 9%
	 * 2018年9月4日 下午4:07:39
	 */
	public int findTargetSumWays(int[] nums, int S) {
        help(nums,0,0,S);
        return this.res;
    }	
	public void help(int[] nums,int index,int sum,int S) {
		if(index==nums.length) {
			if(S==sum)
				this.res++;
			return ;
		}
		help(nums,index+1,sum+nums[index],S);
		help(nums,index+1,sum-nums[index],S);
	}
}
